package leetcode.editor.cn;//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
// 
//
// 示例 2： 
//
// 
//输入：height = [4,2,0,3,2,5]
//输出：9
// 
//
// 
//
// 提示： 
//
// 
// n == height.length 
// 1 <= n <= 2 * 104 
// 0 <= height[i] <= 105 
// 
// Related Topics 栈 数组 双指针 动态规划 单调栈 
// 👍 3096 👎 0


import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution42 {

    public int trap(int[] height) {
        int len=height.length;
        if(len<=1) return 0;
        int res=0;
        int leftMax=0,rightMax=0,left=0,right=len-1;
        while (left<right){
            leftMax=Math.max(leftMax,height[left]);
            rightMax=Math.max(rightMax,height[right]);
            //height[left]<height[right]->leftMax<rightMax->height[i]左侧最大值<右侧最大值
            //这样就可以确定left位置可接雨水，因为res[i]=MIN(height[i]左侧最大值,右侧最大值)
            //反之可以确定right位置的雨水
            if(height[left]<height[right]){
                res+=leftMax-height[left++];
            }
            else{
                res+=rightMax-height[right--];
            }
        }
        return res;
    }
    //dp[i]，第i格能接的雨水，=MIN(MAX(dp[0,i-1],dp[i+1,len-1]))
    //max[i][0],i左边最大值
    //max[i][0]=Math.max(max[i-1][0],height[i-1])
    public int trap00(int[] height) {
        int len=height.length;
        if(len<=1) return 0;
        int[][] max=new int[len][2];
        max[0][0]=0;
        max[len-1][1]=0;
        for (int i = 1; i < len; i++)
            max[i][0]=Math.max(max[i-1][0],height[i-1]);
        for (int i = len-2; i >=0; i--)
            max[i][1]=Math.max(max[i+1][1],height[i+1]);
        int res=0,tmp;
        for (int i = 0; i < len; i++){
            tmp=Math.min(max[i][0],max[i][1])-height[i];
            res+=tmp>0?tmp:0;
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
